// https://leetcode.cn/problems/minimum-path-sum/
#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
		int m = grid.size(); // 行
		int n = grid[0].size(); // 列 

		for(int i = 1; i < m; i++){
			grid[i][0] = grid[i][0] + grid[i-1][0];
		}
		for(int j = 1; j < n; j++){
			grid[0][j] = grid[0][j] + grid[0][j-1];
		}
		for(int i = 1; i < m; i++){
			for(int j = 1; j < n; j++){
				grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j];
			}
		}

		return grid[m-1][n-1];
    }
};

int main(){
	vector<vector<int>> grid = {{1,3,1},{1,5,1}};
	int m = grid.size(); // 行
		int n = grid[0].size(); // 列 
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cout << grid[i][j] << ",";
		}
		cout << endl;
	}
	Solution so;
	int a = so.minPathSum(grid);
	cout << a << endl;
	return 0;
}